﻿#ifndef _MY_VECTOR_
#define _MY_VECTOR_

#include <memory>

namespace Break {
template <typename T> class vector {
public:
  // 类型提取
  using value_type = T;
  using pointer = value_type *;
  using const_pointer = const value_type *;
  using iterator = value_type *;
  using const_iterator = const value_type *;
  using reference = value_type &;
  using const_reference = const value_type &;
  using size_type = std::size_t;
  using difference_type = ptrdiff_t;

private:
  // 开始指针
  iterator start;
  // 结束指针
  iterator finish;
  // 边界指针
  iterator end_of_storage;

  /**
   * @brief 分配内存空间并执行初始化操作
   *
   * @param size 分配空间大小
   * @param value 值
   */
  void fill_initialize(size_type size, const T &value) {
    start = new T[size];
    if (start == nullptr)
      return;
    finish = start + size;
    end_of_storage = finish;
    fill(start, finish, value);
  }

private:
  /**
   * @brief 将 (first, last) 数据复制到 result 数组中
   * @return pointer 尾迭代器
   */
  inline pointer copy(const pointer first, const pointer last,
                      const pointer result) {
    pointer tmp = result;
    for (pointer cur = first; cur != last; ++cur)
      *(tmp++) = *(cur);
    return tmp;
  }

  /**
   * @brief [first, last) 范围填充
   *
   * @tparam ForwardIterator 迭代器，支持正向迭代
   * @tparam T 填充值类型
   */
  template <class ForwardIterator, class T>
  void fill(ForwardIterator first, ForwardIterator last, const T &value) {
    for (; first != last; ++first) {
      *first = value;
    }
  }

  /**
   * @brief 填充 n 个元素到 first 迭代器中
   *
   * @tparam ForwardIterator
   * @tparam Size
   * @tparam T
   */
  template <class ForwardIterator, class Size, class T>
  ForwardIterator fill_n(ForwardIterator first, Size n, const T &value) {
    ForwardIterator cur = first;
    for (; n > 0; --n, ++cur) {
      *cur = value;
    }
    return cur;
  }

  /**
   * @brief 计算迭代器距离，引用
   *
   */
  template <class InputIterator, class Size>
  void Distance(InputIterator first, InputIterator last, Size &n) {
    while (first != last) {
      ++first;
      ++n;
    }
  }

  /**
   * @brief 拷贝并分配内存，用于拷贝构造函数
   *
   * @tparam ForwardIterator 迭代器，支持正向迭代
   * @return iterator 返回堆头指针
   */
  template <class ForwardIterator>
  ForwardIterator copy_and_allocate(difference_type size, ForwardIterator first,
                                    ForwardIterator last) {
    ForwardIterator result = new T[size];
    if (result == nullptr)
      return nullptr;
    for (ForwardIterator iter = result; first != last; ++first, ++iter) {
      *iter = *first;
    }
    return result;
  }

  /**
   * @brief 从 result 开始向前复制值
   */
  template <class BidirectionalIterator1, class BidirectionalIterator2>
  BidirectionalIterator2 copy_backward(BidirectionalIterator1 first,
                                       BidirectionalIterator1 last,
                                       BidirectionalIterator2 result) {
    while (first != last)
      *--result = *--last;
    return result;
  }

private:
  template <class InputIterator>
  void range_initialize(InputIterator first, InputIterator last) {
    size_type n = 0;
    Distance(first, last, n);
    start = copy_and_allocate(n, first, last);
    finish = start + n;
    end_of_storage = finish;
  }

  void insert_aux(iterator position, const T &value) {
    if (finish != end_of_storage) {
      // 数组中还有空间
      // 需要将插入位置的元素后移
      *finish = *(finish - 1);
      ++finish;
      T value_copy = value;
      copy_backward(position, finish - 2, finish - 1);
      *position = value_copy;
    } else {
      // 数组中空间不足
      const size_type old_size = size();
      const size_type new_size = old_size != 0 ? 2 * old_size : 1;
      iterator new_start = new T[new_size];
      iterator new_finish = new_start;
      // for (iterator cur = start; cur != position; ++cur)
      //   *(new_finish++) = *(cur);
      new_finish = copy(start, position, new_start);
      *new_finish = value;
      ++new_finish;
      // for (iterator cur = position; cur != finish; ++cur)
      //   *(new_finish++) = *(cur);
      copy(position, finish, new_finish);
      destory(begin(), end());
      deallocate();
      start = new_start;
      finish = new_finish;
      end_of_storage = new_start + new_size;
    }
  }

  void insert(iterator position, size_type n, const T &value) {
    if (n != 0) {
      if (size_type(end_of_storage - finish) >= n) {
        // 数组内存充足时
        // 只需要将 position 开始的元素复制进数组中
        T value_copy = value;
        const size_type elems_after = finish - position;
        iterator old_finish = finish;
        if (elems_after > n) {
          copy(finish - n, finish, finish);
          finish += n;
          copy_backward(position, old_finish - n, old_finish);
          fill(position, position + n, value_copy);
        } else {
          fill_n(finish, n - elems_after, value_copy);
          finish += n - elems_after;
          copy(position, old_finish, finish);
          finish += elems_after;
          fill(position, old_finish, value_copy);
        }
      } else {
        // 数组内存不足
        const size_type old_size = size();
        const size_type new_size = old_size + (old_size < n ? n : old_size);
        iterator new_start = new T[new_size];
        iterator new_finish = new_start;
        new_finish = copy(start, position, new_start);
        new_finish = fill_n(new_finish, n, value);
        new_finish = copy(position, finish, new_finish);
        destory(start, finish);
        deallocate();
        start = new_start;
        finish = new_finish;
        end_of_storage = new_start + new_size;
      }
    }
  }

private:
  /**
   * @brief 释放内存
   */
  void deallocate(pointer p, difference_type /* n */) {
    if (p != nullptr)
      delete[] p;
  }
  void deallocate() { deallocate(start, end_of_storage - start); }
  void destory(pointer pointer) { pointer->~T(); }
  void destory(iterator first, iterator last) {
    for (; first < last; ++first)
      destory(&*first);
  }

public:
  vector() : start(nullptr), finish(nullptr), end_of_storage(nullptr) {}
  explicit vector(size_type size) { fill_initialize(size, T()); }
  vector(size_type size, const T &value) { fill_initialize(size, value); }
  vector(int size, const T &value) { fill_initialize(size, value); }
  vector(long size, const T &value) { fill_initialize(size, value); }
  template <class InputIterator>
  vector(InputIterator first, InputIterator last) {
    range_initialize(first, last);
  }

  vector(vector<T> &other) {
    start = copy_and_allocate(other.cend() - other.cbegin(), other.begin(),
                              other.end());
    finish = start + (other.end() - other.begin());
    end_of_storage = finish;
  }

  ~vector() {
    destory(start, finish);
    deallocate(start, end_of_storage - start);
    start = finish = end_of_storage = nullptr;
  }

public:
  /**
   * @brief 向尾部添加元素
   *
   * @param value
   */
  void push_back(const T &value) {
    if (finish != end_of_storage) {
      // 内存足够
      *finish = value;
      ++finish;
    } else {
      // 内存不足
      insert_aux(end(), value);
    }
  }

  /**
   * @brief 尾部抛出元素
   *
   */
  void pop_back() {
    --finish;
    destory(finish);
  }

  /**
   * @brief 删除指定位置元素
   *
   * @param position 需要删除的元素迭代器
   * @return iterator
   */
  iterator earse(iterator position) {
    if (position + 1 != end()) {
      // 将 position 之后的值复制到 position 中
      copy(position + 1, finish, position);
    }
    --finish;
    destory(finish);
    return position;
  }

  /**
   * @brief 删除指定范围的元素
   *
   * @return iterator
   */
  iterator earse(iterator first, iterator last) {
    // 将 last 之后的值复制到 first
    iterator i = copy(last, finish, first);
    destory(i, finish);
    finish = finish - (last - first);
    return first;
  }

  /**
   * @brief 在 position 之前插入
   *
   * @param position 插入位置
   * @param value 值
   * @return iterator 返回插入元素迭代器
   */
  iterator insert(iterator position, const T &value) {
    size_type n = position - begin();
    if (finish != end_of_storage && position == end()) {
      // 有空位且在末尾插入
      *finish = value;
      ++finish;
    } else {
      insert_aux(position, value);
    }
    return begin() + n;
  }

  iterator insert(iterator position) { return insert(position, T()); }

  /**
   * @brief 范围插入
   */
  template <class InputIterator>
  void insert(iterator position, InputIterator first, InputIterator last) {
    for (; first != last; ++first) {
      position = insert(position, *first);
      ++position;
    }
  }

  void resize(size_type new_size, const T &value) {
    if (new_size < size()) {
      earse(begin() + new_size, end());
    } else {
      insert(end(), new_size - size(), value);
    }
  }

  void resize(size_type new_size) { resize(new_size, T()); }

  /**
   * @brief 清空
   *
   */
  void clear() { earse(begin(), end()); }

public:
  iterator begin() { return start; }
  iterator end() { return finish; }

  const_iterator cbegin() const { return start; }
  const_iterator cend() const { return finish; }

  size_type size() { return size_type(end() - begin()); }
  size_type capacity() { return size_type(end_of_storage - begin()); }

  bool empty() const { return begin() == end(); }

  reference operator[](size_type n) { return *(begin() + n); }
  const_reference operator[](size_type n) const { return *(begin() + n); }

  reference front() { return *begin(); }
  const_reference front() const { return *begin(); }
  reference back() { return *(end - 1); }
  const_reference back() const { return *(end - 1); }

public:
  template <class T> vector<T> &operator=(const vector<T> &x) {
    if (&x != this) {
      if (x.size() > capacity()) {
        iterator tmp =
            copy_and_allocate(x.end() - x.begin(), x.begin(), x.end());
        destory(start, finish);
        deallocate();
        start = tmp;
        end_of_storage = start + (x.end() - x.begin());
      } else if (size() >= x.size()) {
        iterator i = copy(x.begin(), x.end(), begin());
        destory(i, finish);
      } else {
        copy(x.begin(), x.begin() + size(), start);
        copy(x.begin() + size(), x.end(), finish);
      }
      finish = start + x.size();
    }
    return *this;
  }
};
} // namespace Break

#endif // _MY_VECTOR_